#include "tree_node.h"
#include <queue>
#include <iostream>

bool is_complete(const std::shared_ptr<Node>& root){
	if(!root)
		return false;
	std::queue<std::shared_ptr<Node> > q;
	q.push(root);
	int curr = 1;
	while(!q.empty()){
		int next = 0;
		for (int i = 0; i<curr; ++i){
			std::shared_ptr<Node> node = q.front();
			q.pop();
			if(node->left) {
				++next;
				q.push(node->left);
			}
			if(node->right){
				++next;
				q.push(node->right);
			}
		}
		if (next == 0)
			return true;
		if (next != 2*curr)
			return false;
		curr = 2*curr;
	}
	return true; //unreachable
}

bool is_full(const std::shared_ptr<Node>& root){
	if(!root)
		return false;
	std::queue<std::shared_ptr<Node> > q;
	q.push(root);
	while(!q.empty()){
		std::shared_ptr<Node> node = q.front();
		q.pop();
		if(node->left && node->right){
			q.push(node->left);
			q.push(node->right);
		}
		else if(!node->left && !node->right) {
			continue;
		}
		else{
			return false;
		}
	}
	return true;
}

bool is_nearly_complete(const std::shared_ptr<Node>& root){
	if(!root)
		return false;
	std::queue<std::shared_ptr<Node> > q;
	q.push(root);
	bool complete = true;
	while(!q.empty()){
		std::shared_ptr<Node> node = q.front();
		q.pop();
		if(complete) {
			if(node->left && node->right){
				q.push(node->left);
				q.push(node->right);
			}
			else if(node->left && !node->right) {
				q.push(node->left);
				complete = false;
			}
			else if(!node->left && !node->right){
				complete = false;
			}
			else
				return false;
		}
		else {
			if(node->left || node->right)
				return false;
		}
	}
	return true;
}

void test_internal(std::string& str){
	std::shared_ptr<Node> root = preorder_deserialize(str);
	print_tree(root);
	if (is_complete(root))
		std::cout << "It is a complete tree" << std::endl;
	else
		std::cout << "It is not a complete tree" << std::endl;
	if (is_full(root))
		std::cout << "It is a full tree" << std::endl;
	else
		std::cout << "It is not a full tree" << std::endl;
	if (is_nearly_complete(root))
		std::cout << "It is a nearly complete tree" << std::endl;
	else
		std::cout << "It is not a nearly complete tree" << std::endl;
}

void test_complete_full(){
	std::string str = "3 1 0 # # 2 # # 5 4 # # 6 # #";
	test_internal(str);

	str = "1 2 4 # # # 3 # #";
	test_internal(str);

	str = "4 2 1 # # 3 # # 5 # #";
	test_internal(str);

	str = "3 2 1 # # # 4 # 5 # #";
	test_internal(str);

	str = "5 3 1 0 # # 2 # # 4 # # 6 # #";
	test_internal(str);
}